Baby-step Giant-step
概要
関数$ f \colon X \rightarrow X について、$ f^n(s)=g となる最小の非負整数$ n を求めるアルゴリズム。
条件は
1. $ f^N(x) = x なる$ N が存在する（計算に使う$ N は、これを満たす最小値以上なら何でもOK）
2. $ f(x)の計算が速い
3. $ M を決めておいて、$ f^M(x) の計算も速い
4. $ x \in X が$ Y \subset X に属するかの計算も速い
5. 逆関数$ f^{-1}(x) が存在する（計算できる必要はない）
手順
$ n = iM - j \quad (1 \le i \le \lceil N/M \rceil, \; 1 \le j \le M) とする。（この$ i, j で$ 0 \le n \le N すべて調べられるし、条件1. からこの範囲を調べられれば十分）
$ f^{iM-j}(s) = g
両辺を$ f^j すると
$ f^{iM}(s) = f^j(g)
これを満たす$ i, j を求めれば、条件5.から$ f^{iM-j}(s) = g になってくれるので
$ f^j(g) を$ 1 \le j \le M について求めておく（条件2.）
$ f^{iM}(s) を$ 1 \le i \le \lceil N/M \rceil について求めつつ、（条件3.）
$ = f^j(g) となる$ j があったか探す（条件4.）
実装
code:BaGa.py
def BsGs(s, g):
# settings
def f(x): # f(x) を定義
return x
N = 10**9 # f^m(x) = x なる m <= N が存在する N
M = int(N**0.5)+1
def fM(x): # f^M(x) も定義
return x
# Baby-step
X = dict() # f^j(g) を格納するところ
for j in range(M):
g = f(g)
# Giant-step
for i in range(-((-N)//M)):
s = fM(s)
if s in X:
return -1
計算量
$ f(x) ,\; f^M(x),\; x \in Y それぞれの計算量を$ O(F_1),\;O(F_2),\;O(F_3) とすると、
全体の計算量は$ O(F_1M + (F_2 + F_3)N/M) となる。
（大抵は$ F_1,\;F_2,\;F_3=1 で、$ M = \sqrt N として計算量$ O(\sqrt N) にする）
具体例：離散対数問題
具体例として、$ a^n = b \pmod c を解くことを考えてみる。
素数mod $ c \in \mathbb P
色々困るので$ a = 0 は別で考える。
$ a \not= 0 で$ f(x) = ax \mod c とすると、
$ f^n(s) = a^ns から、$ s = 1
それと$ g = c
となって、
1. $ f^N(x) = x なる$ N の存在：$ c が素数なので、$ f^{c-1}(x) = a^{c-1}x = x
2. $ f(x) の計算：余裕で$ O(1)
3. $ f^M(x) の計算：$ a^M を計算しておけばそれをかけるだけの$ O(1)
4. $ x \in Xの判定：setやdict使って$ O(1) とか$ O(\log M) とか
5. $ f^{-1}(x) の存在：$ c が素数なので、$ f^{-1}(x) = a^{c-2}x
ということで、Baby-step Giant-stepが適用できる。
code:ModLog.py
# BsGs(1, b, c, a) で呼ぶ
def BsGs(s, g, P, A):
# settings
def f(x): # f(x) を定義
return A * x % P
N = P # f^m(x) = x なる m <= N が存在する N
M = int(N**0.5)+1
AM = pow(A, M, P)
def fM(x): # f^M(x) も定義
return AM * x % P
# Baby-step
X = dict() # f^j(g) を格納するところ
for j in range(M):
g = f(g)
# Giant-step
for i in range(-((-N)//M)):
s = fM(s)
if s in X:
return -1
合成数mod
Baby-step Giant-stepの考察ではないが、一応
$ c が合成数（または1）のとき、$ a の値によっては$ f(x) = ax の逆関数が存在しないことがある。
$ c = 1 は常に$ 0=0 になるだけなので、$ n = 0 でOK。以下$ c \gt 1 を考える。
再帰解法
なので、$ \gcd(a, c) = g \gt 2 のときになんとかして$ g = 1 になるように変形していく。
$ a = a'g,\;c=c'g として、$ a^n = b \pmod c に代入すると、
$ (a'g)^n = b \pmod {c'g}
つまり、
$ (a'g)^n - b = mc'g
なる整数$ m が存在することになる。$ b = 1 のときは$ n = 0 が答え。（$ a = 0 がめんどくさいとかあるけどなんかうまいことif分岐しよう）
そうでないときは、$ b も$ g の倍数になってる必要があるので、$ b が$ g で割り切れないときは解なし。
割り切れるときは$ b = b'g として、
$ a'g(a'g)^{n-1} - b'g = mc'g
$ a'(a'g)^{n-1} - b' = mc'
$ \therefore \; a'(a'g)^{n-1} = b' \pmod {c'}
$ a' と$ c' は互いに素なので、$ a' での除算ができて、
$ a^{n-1} = b'a'^{-1} \pmod {c'}
ということで、除数が一回り小さい問題に変形できた。
（$ a'^{-1} を求める部分は、拡張ユークリッドの互除法を使って$ O(\log c') でできる。）
あとはこれを$ \gcd(a, c) = 1 になるまで再帰的に繰り返すだけ。
……再帰はPyPy的に面倒なので、非再帰でできるように更に考察していく。
非再帰解法へ
上記の操作1回で$ (a, c) \rightarrow (a, c/g) と変化する。ここから再び操作する必要がある条件を考えると、
$ a,c の共通の素因数$ p で、$ a を割れる回数より$ c を割れる回数が多いものがある
となる。つまり、ベストな$ g の値は、いい感じに大きい$ d を持ってきて$ g = \gcd(a^d, c) となる。
「いい感じに大きい$ d 」はどれくらいか？→$ c の素因数$ p で割り切れる回数が最多になるやつ→$ \log _2 c 以上
この$ d,g を使って整理していくと、
$ a^da^{n-d} = b \pmod c
$ b は$ g で割り切れる必要があって、
$ (a^d/g)a^{n-d} = b/g \pmod {c/g}
$ a^{n-d} = b/g\:(a^d/g)^{-1} \pmod {c/g}
を解けばいい。まとめると、
1. $ d = \lfloor \log_2c \rfloor として、$ 0 \le n \lt d について解になるか確認する。解けたら終わり
2. $ g = \gcd(a^d, c) として、$ a^{n-d} = b/g\:(a^d/g)^{-1} \pmod {c/g} を解く。
（$ a^{n-d} = b/g\:(a^d/g)^{-1}=b\:(a^d)^{-1} \pmod {c/g} とできる。$ (a^d)^{-1} できるのか不安になるが、$ c/g は$ a と共通する素因数を割られ切ってるので、$ \gcd(a^d, c/g) となる。（で合ってる？））
a, cが互いに素になった後
$ f(x) = ax \mod c として条件1, 5の確認ができれば、あとは素数のときとほぼ同じ
1. $ f^N(x) = x なる$ N の存在：$ a, c が互いに素なので、オイラーのφ関数より$ f^{\varphi(c)}(x) = x となる。 5. $ f^{-1}(x) の存在：$ a^{\varphi(c)-1} = a^{-1} \pmod c から$ f^{-1}(x) = a^{\varphi(c)-1}x
ということで、条件を満たしている。$ \varphi(c) \lt c なので、あとは$ N = c として計算すればいい。
問題
参考